import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

    }

    public List<Integer> countSmaller(int[] nums) {
        /**
         * 计算右侧小于当前元素的个数*/
        // 1 预处理
        int n = nums.length;
        int[] count = new int[n];
        // -将nums修改为int[n][2]结构，其中arr[x][0]表示值，arr[x][1]表示原索引
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }
        List<Integer> retList = new LinkedList<>();
        // 2 归并解决
        mergeSort(0, n-1, arr, count);
        // 3 返回值
        for(int e: count) {
            retList.add(e);
        }
        return retList;
    }

    public static int[][] tempArray = new int[10_0000][2];

    public static void mergeSort(int left, int right, int[][] nums, int[] count) {
        // 1 递归出口
        if(left >= right) {
            return;
        }
        // 2 递归左右分别计数
        int mid = left + (right - left) / 2;
        mergeSort(left, mid, nums, count);
        mergeSort(mid+1, right, nums, count);
        // 3 合并a、b计数
        int baseIndex = left;
        int n = right - left + 1;
        int i = 0;
        // -临时写入
        int left2 = mid + 1;
        while(left <= mid && left2 <= right) {
            if(nums[left][0] <= nums[left2][0]) {
                tempArray[i][0] = nums[left2][0];
                tempArray[i++][1] = nums[left2++][1];
            } else {
                // -利用单调性快速计算
                count[nums[left][1]] += (right - left2 + 1);
                tempArray[i][0] = nums[left][0];
                tempArray[i++][1] = nums[left++][1];
            }
        }
        while(left <= mid) {
            tempArray[i][0] = nums[left][0];
            tempArray[i++][1] = nums[left++][1];
        }
        while(left2 <= right) {
            tempArray[i][0] = nums[left2][0];
            tempArray[i++][1] = nums[left2++][1];
        }
        // -真实写入
        for(int j = 0; j < n; j++) {
            nums[baseIndex + j][0] = tempArray[j][0];
            nums[baseIndex + j][1] = tempArray[j][1];
        }
    }
}
